package com.sxu.greedy.day5;

/**
 * 397 整数替换
 *  贪心算法
 */
public class Test24_3 {
    public int integerReplacement(int n) {
        int ret = 0;
        while (n > 1) {
            if (n % 2 == 0) {
                n /= 2;
                ret++;
            } else {
                if(n == 3){
                    ret += 2;
                    n = 1;
                } else if(n % 4 == 1){
                    n = n / 2; // n / 2 相当于 -1再/2
                    ret += 2;
                } else {
                    n = n / 2 + 1; // n + 1可能会溢出，所以先/2再+1
                    ret += 2;
                }
            }
        }
        return ret;
    }
}
